package _树_hard;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class _tree {

    // 114：二叉树展开为链表：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
    public void flatten1(TreeNode root) {
        if (root == null) return;
        // 迭代法 前序遍历 和 操作同时进行
        // 栈：后进先出的数据结构，，栈里存的是子树
        // 对每一个节点应该做什么事情
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        // 存一个前驱节点
        TreeNode pre = null;
        while (!st.isEmpty()) {
            TreeNode cur = st.pop();
            if (pre != null) {
                pre.left = null;
                pre.right = cur;
            }
            // 把右子树全部暂存到栈里，下一次弹出 操作左子树
            if (cur.right != null) st.push(cur.right);
            if (cur.left != null) st.push(cur.left);
            pre = cur;
        }
    }

    public void flatten(TreeNode root) {
        if (root == null) return;
        // 递归法，此时左右节点已经是平的了
        flatten(root.left);
        flatten(root.right);
        // 把自己打平
        TreeNode l = root.left, r = root.right, p = root;
        root.left = null;
        root.right = l;
        while (p.right != null) {
            p = p.right;
        }
        p.right = r;
    }

    // 263 二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
    TreeNode ans;

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return ans;
    }

    // 递归函数的定义是判断以当前节点为根节点的树，是否包含 p 或 q
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件
        if (root == null) return false;
        boolean l = dfs(root.left, p, q);
        boolean r = dfs(root.right, p, q);
        // p q 都在左右子树上面 || 当前节点是p 或者 q的其中一个，
        // 这是收集答案的地方
        if (l && r || (root.val == p.val || root.val == q.val) && (l || r)) {
            ans = root;
        }
        // 单层递归逻辑
        return l || r || root.val == p.val || root.val == q.val;
    }

    // 二叉树的后序遍历。非递归 145
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) return res;
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode node = st.pop();
            res.add(node.val);
            if (node.left != null) st.push(node.left);
            if (node.right != null) st.push(node.right);
        }
        Collections.reverse(res);
        return res;
    }

    // 112:路径总和：https://leetcode.cn/problems/path-sum/
    // 每一次去看子节点的目标值应该是多少
    // 带着参数去递归
    public boolean hasPathSum1(TreeNode root, int targetSum) {
        if (root == null) return false;
        // 到达叶子节点
        if (root.left == null && root.right == null)
            return targetSum == root.val;

        int target = targetSum - root.val;
        boolean l = hasPathSum1(root.left, target);
        boolean r = hasPathSum1(root.right, target);
        return l || r;
    }


    // 652:todo 寻找重复的子树 ：https://leetcode.cn/problems/find-duplicate-subtrees/?envType=problem-list-v2&envId=tree
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

        return null;
    }
    // _LCR_051:二叉树中的最大路径和： https://leetcode.cn/problems/jC7MId/description/
    public int maxPathSum(TreeNode root) {
        // todo
        return 0;
    }

    // 二叉树，有递有归
    // 865：具有所有最深节点的最小子树：https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return null;
    }

    // 1080:根到叶子路径上的不足节点
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        // TODO
        return null;
    }


    //993：二叉树的堂兄弟节点
    public boolean isCousins(TreeNode root, int x, int y) {
        // TODO
        return false;
    }
}













